/**
 * 
 */
package dp.passed;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author xyyi
 *
 */
public class ActivitiesSelection {

	class Activity {
		int start = 0;
		int end = 0;
		int weight = 0;

		public Activity(int start, int end, int weight) {
			this.start = start;
			this.end = end;
			this.weight = weight;
		}

		@Override
		public boolean equals(Object o) {
			if (o == this)
				return true;
			if (!(o instanceof Activity))
				return false;

			Activity act = (Activity) o;
			return this.start == act.start && this.end == act.end
					&& this.weight == act.weight;
		}

		@Override
		public int hashCode() {
			int hash = 17;
			hash = hash * 31 + this.start;
			hash = hash * 31 + this.end;
			hash = hash * 31 + this.weight;

			return hash;
		}
	}

	class ActivityEndComparator implements Comparator<Activity> {

		@Override
		public int compare(Activity o1, Activity o2) {
			if (o1 == o2)
				return 0;
			if (o1 == null)
				return -1;
			if (o2 == null)
				return 1;
			if (o1.end < o2.end)
				return -1;
			if (o1.end > o2.end)
				return 1;

			return 0;
		}
	}

	// Greedy
	// http://www.geeksforgeeks.org/greedy-algorithms-set-1-activity-selection-problem/
	public List<Activity> activitiesSelect(List<Activity> activities) {
		List<Activity> selectedActivies = new ArrayList<Activity>();
		if (activities == null || activities.size() == 0)
			return selectedActivies;

		Collections.sort(activities, new ActivityEndComparator());
		selectedActivies.add(activities.get(0));
		for (int i = 1; i < activities.size(); i++) {
			if (activities.get(i).start >= activities.get(i - 1).end) {
				selectedActivies.add(activities.get(i));
			}
		}

		return selectedActivies;
	}

	/*
	 * DP
	 * http://dirk.liveforchrist.tw/?p=178
	 * 1 Sort activities by end increasedly.
	 * 2 compute q, define q(j) for all index i < j such that job i is ended before j
	 * 3 opt(0) = 0
	 *   opt(j) = max(w(j) + opt(q(j)) , opt(j - 1)) 
	 *   Let OPT(j) = value of optimal solution to the problem consisting of
	job requests {1, 2, . . . , j }.
	 */
	public List<Activity> weightActivitiesSelect(List<Activity> activities) {
		List<Activity> selectedActivies = new ArrayList<Activity>();
		if (activities == null || activities.size() == 0)
			return selectedActivies;

		// computer 1
		int[] q = new int[activities.size() + 1];

		Map<Activity, Activity> backtrack = new HashMap<Activity, Activity>();
		boolean[] included = new boolean[activities.size() + 1];
		int[] opt = new int[activities.size() + 1];

		opt[0] = 0;
		for (int i = 1; i < opt.length; i++) {
			if (activities.get(i - 1).weight + opt[q[i]] > opt[i - 1]) {
				opt[i] = activities.get(i - 1).weight + opt[q[i]];
				backtrack.put(activities.get(i - 1), activities.get(q[i] - 1));
				included[i] = true;
			} else {
				opt[i] = opt[i - 1];
				backtrack.put(activities.get(i - 1), activities.get(i - 2));
			}
		}

		return null;
	}

	/**
	 * 
	 */
	public ActivitiesSelection() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
